沉寂了一段时间，继续学习。
算法这个系列我想分享很久了，奈何本身对算法不是特别了解，又找不到合适的载体来分享。
最近看了本有趣的算法书， 文中通过图文并茂的讲解给我很大启发，尝试着分享下
需要注意的是， 文中各个算法的写法不是简单的拷贝，算理解思想后拿Python3重新写了遍，分享的代码和书中的例子也稍有不同，加了些日常工作中会做的处理，如有不适，请联系我。
二分查找 –仅当列表是有序的时候才能用
思想：
1.目标是找数组中的某一个元素，暂叫item
2.找出整个数组中间的那个元素，它下标mid，数组被它一分为二
3.比较下标mid对应的元素和item，如果mid对应的元素大，查找范围缩小到mid前面的那一半数组，反之，缩小到mid后的那一半数组
4.重复3，直到item==mid
对于包含N个元素的列表，用二分查找最多需要log2 N 步。（对数是幂运算的逆运算）
大O表示法指出了算法有多快。例如，假设列表包含n 个元素。简单查找需要检查每个元素，因此需要执行n 次操作。使用大O表示法，这个运行时间为O (n )。单位秒呢？没有——大O表示法指的并非以秒为单位的速度。大O表示法让你能够比较操作数，它指出了算法运行时间的增速 。
再来看一个例子。为检查长度为n 的列表，二分查找需要执行log n 次操作。使用大O表示法，这个运行时间怎么表示呢？O (log n )。一般而言，大O表示法按从快到慢的顺序列出了你经常会遇到的5种大O运行时间。
O (log n )，也叫对数时间 ，这样的算法包括二分查找。
O (n )，也叫线性时间 ，这样的算法包括简单查找。
O (n * log n )，这样的算法包括第4章将介绍的快速排序——一种速度较快的排序算法。
O (n 2 )，这样的算法包括第2章将介绍的选择排序——一种速度较慢的排序算法。
O (n !)，这样的算法包括接下来将介绍的旅行商问题的解决方案——一种非常慢的算法。
大O表示法指出了最糟情况下的运行时间.
选择排序
思想：
找出数组中最小的元素
把数组中最小的元素pop出来到新的数组里。
重复以上操作直到原数组为空
需要存储多个元素时，可使用数组或链表。
数组的元素都在一起。
链表的元素是分开的，其中每个元素都存储了下一个元素的地址。
数组的读取速度很快。
链表的插入和删除速度很快。
在同一个数组中，所有元素的类型都必须相同（都为int、double等）
数字和链表区别：
数组： 连续空间， 预留空间， 查找方便， 插入麻烦，必须移动后面的所有元素，如果没有空间，必须将数组复制到其他地方。
链表： 分散空间，查找麻烦，插入方便，只需移动前面元素指向的地址。
数组 链表
读取 O（1） O（n）
插入 O（n） O（1）
删除 O（n） O(1)
访问 顺序访问 随机访问
O(n)=线性时间
O(1)=常量时间
递归
每个递归函数都有两部分：基线条件 （base case）和递归条件 （recursive case）。递归条件指的是函数调用自己，而基线条件则指的是函数不再调用自己，从而避免形成无限循环。
我们拿 最大公约数 来举例：
思想：
假定x > y（如果x < y，则互换）
求x对y的余数，假定余数为z
求y与z的最大公约数即为x，与y的最大公约数
0没有公约数
最小公倍数 ：
思想：
两个数(x, y)的最小公倍数数的算法为：两个数相乘再除以他们的最大公约数
0没有公倍数
公约数，公倍数，适用于自然数。
快速排序
思想：
少于2个元素的数组不需要排序
找一个元素作为基数
小于基数的放一个数组
大于基数的放一个数组
针对小于基数的数组做快速排序，暂且叫low
针对大于基数的数组做快速排序, 暂且叫high
最终排序后的 low + 【基数】+ high，就是排好序的数组
总结下：
D&C算法（divided and conqure）是递归的。使用D&C解决问题的过程包括两个步骤。
(1) 找出基线条件，这种条件必须尽可能简单。
(2) 不断将问题分解（或者说缩小规模），直到符合基线条件。
散列表（Hash Table）
散列函数：
散列函数是这样的函数，即无论你给它什么数据，它都还你一个数字。
散列函数总是将同样的输入映射到相同的索引。例如你每次输入iTesting，它返回你的总是同一个数字。
散列函数将不同的输入映射到不同的索引。比如iTesting对应6， python对于0. 如果散列函数将不同的键映射到同一个位置，就在这个位置存储一个链表。
散列函数知道数组有多大，只返回有效的索引。如果数组包含5个元素，散列函数就不会返回无效索引100。
结合使用散列函数和数组创建了一种被称为散列表 （hash table）的数据结构。
不需要自己去实现散列表，任一优秀的语言都提供了散列表实现。Python提供的散列表实现为字典 ，你可使用函数dict 来创建散列表。
散列表被用于大海捞针式的查找，散列表适合用于：
模拟映射关系；
防止重复；
缓存/记住数据，以免服务器再通过处理来生成它们。
总结：
你可以结合散列函数和数组来创建散列表。
冲突很糟糕，你应使用可以最大限度减少冲突的散列函数。
散列表的查找、插入和删除速度都非常快。
散列表适合用于模拟映射关系。
一旦填装因子超过0.7，就该调整散列表的长度（通常将数组长度加倍）。
散列表可用于缓存数据（例如，在Web服务器上）。
散列表非常适合用于防止重复。
（填装因子是数组中被占用的位置，例如大小为3的数字，有2个被占用，则填装因子为2/3）
